package 双指针技巧与相关题目;

// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/

public class Code01_SortArrayByParityII {

    // 时间复杂度O(n)，额外空间复杂度O(1)
    public static int[] sortArrayByParityII(int[] nums) {
        int look = nums.length - 1;
        // even：偶数位来到0位置，odd：奇数位来到1位置
        // 奇数不越界并且偶数不越界就继续，有一个越界就停
        for (int even = 0, odd = 1; even < nums.length && odd < nums.length; ) {
            // 偶数
            if ((nums[look] & 1) == 0) {
                // 发货
                swap(nums, even, look);
                even += 2;
            }else {
                swap(nums, odd, look);
                odd += 2;
            }
        }
        return nums;
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
